#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

struct Node {
	int val;
	struct Node* next;
	struct Node* random;
	
};

struct Node* ListInit()
{
	struct Node* list1 = (struct Node*)malloc(sizeof(struct Node));
	struct Node* list2 = (struct Node*)malloc(sizeof(struct Node));
	struct Node* list3 = (struct Node*)malloc(sizeof(struct Node));
	struct Node* list4 = (struct Node*)malloc(sizeof(struct Node));
	struct Node* list5 = (struct Node*)malloc(sizeof(struct Node));
	list1->val = 7;
	list2->val = 13;
	list3->val = 11;
	list4->val = 10;
	list5->val = 1;
	list1->next = list2;
	list2->next = list3;
	list3->next = list4;
	list4->next = list5;
	list5->next = NULL;
	list1->random = NULL;
	list2->random = list1;
	list3->random = list5;
	list4->random = list3;
	list5->random = list1;

	return list1;

}

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
    {
        return NULL;
    }
    struct Node* cur = head;
    struct Node* newcur = NULL;
    struct Node* newhead = NULL;
    while (cur)
    {
        if (newhead == NULL)
        {
            newhead = (struct Node*)malloc(sizeof(struct Node));
            newhead->val = cur->val;
            newhead->next = cur->next;
            cur->next = newhead;
            newcur = newhead;
        }
        else
        {
            newcur = (struct Node*)malloc(sizeof(struct Node));
            newcur->val = cur->val;
            newcur->next = cur->next;
            cur->next = newcur;
        }
        cur = newcur->next;
    }
    cur = head;
    newcur = newhead;
    while (cur)
    {
        newcur = cur->next;
        if (cur->random == NULL)
        {
            newcur->random = NULL;
        }
        else
        {
            newcur->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    cur = head;
    newcur = newhead;
    while (newcur->next)
    {
        cur->next = newcur->next;
        newcur->next = cur->next->next;
        cur = cur->next;
        newcur = newcur->next;
    }
    cur->next = NULL;
    return newhead;

}





